/**
 * Find the number of integers 1 < n < 10^7, for which n and n + 1 
 * have the same number of positive divisors. For example, 14 has 
 * the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.
 */

#include <iostream>
#include <vector>

// Find the smallest prime factor of each number.
// Use the sieve method.
static void find_smallest_prime_factor(int N, std::vector<int> &spf_index, std::vector<int> &primes)
{
	primes.clear();
	primes.push_back(2);

	spf_index.resize(N+1);
	for (int n = 2; n <= N; n += 2)
		spf_index[n] = 0;
	for (int n = 3; n <= N; n += 2)
		spf_index[n] = -1;

	int p = 3;
	for (; p*p <= N; p += 2)
	{
		if (spf_index[p] == -1) // p is prime
		{
			int i = (int)primes.size();
			primes.push_back(p);
			spf_index[p] = i;
			for (int k = p*p; k <= N; k += 2*p)
			{
				if (spf_index[k] == -1)
					spf_index[k] = i;
			}
		}
	}
	for (; p <= N; p += 2)
	{
		if (spf_index[p] == -1) // p is prime
		{
			int i = (int)primes.size();
			primes.push_back(p);
			spf_index[p] = i;
		}
	}
}

static int count_divisors(int n, const std::vector<int> &spf_index, const std::vector<int> &primes)
{
	int count = 1;
	int last_p = 0, last_k = 0;
	for (int k = n; k > 1; )
	{
		int p = primes[spf_index[k]];
		if (p != last_p)
		{
			count *= (last_k + 1);
			last_p = p;
			last_k = 1;
		}
		else
		{
			++last_k;
		}
		k /= p;
	}
	count *= (last_k + 1);
	return count;
}

void solve_problem_179()
{
#if 0
	const int N = 16;
#else
	const int N = 10000000;
#endif

	std::vector<int> primes;
	std::vector<int> spf_index;
	find_smallest_prime_factor(N, spf_index, primes);

	int count = 0;
#if 0
	for (int n = 2, last = 0; n <= N; n++)
	{
		int t = count_divisors(n, spf_index, primes);
		//std::cout << n << " " << t << std::endl;
		if (t == last)
			++count;
		else
			last = t;
	}
#else
	std::vector<int> divisor_count(N+1);
	divisor_count[1] = 1;
	for (int n = 2; n <= N; n++)
	{
		int k = 1;
		int p = primes[spf_index[n]];
		int t = n / p;
		while (t % p == 0)
		{
			t /= p;
			k++;
		}
		divisor_count[n] = (k + 1) * divisor_count[t];
	}
	for (int n = 2; n < N; n++)
	{
		if (divisor_count[n] == divisor_count[n+1])
			++count;
	}
#endif
	std::cout << count << std::endl;
}